homework 3, version 0

Submission by: Jazzy Doe (jazz@mit.edu)

Homework 3: Structure and Language

18.S191, fall 2020

This notebook contains built-in, live answer checks! In some exercises you will see a coloured box, which runs a test case on your code, and provides feedback based on the result. Simply edit the code, run it, and the check runs again.

For MIT students: there will also be some additional (secret) test cases that will be run as part of the grading process, and we will look at your notebook and write comments.

Feel free to ask questions!

Let's create a package environment:

Exercise 1: Language detection

In this exercise, we are going to create some super simple Artificial Intelligence. Natural language can be quite messy, but hidden in this mess is structure, which we are going to look for today.

Let's start with some obvious structure in English text: the set of characters that we write the language in. If we generate random text by sampling random Unicode characters, it does not look like English:

Instead, let's define an alphabet, and only use those letters to sample from. To keep things simple, we ignore punctuation, capitalization, etc, and only use these 27 characters:

Let's sample random characters from our alphabet:

That alreay looks a lot better than our first attempt! But still, this does not look like English text - we can do better.

English words are not well modelled by this random-latin-characters-model. Our first observation is that some letters are more common than others. To put this observation into practice, we would like to have the frequency table of the latin alphabet. We can search for it online, but it is actually very simple to calculate ourselves! The only thing we need is a representative sample of English text.

The following samples are from Wikipedia, but feel free to type in your own sample! You can also enter a sample of a different language, if that language can be expressed in the latin alphabet.

Remeber that the button on the left of a cell will show or hide the code.

We also include a sample of Spanish, we'll use it later!

Exercise 1.1 - Cleaning data

Looking at the sample, we see that it is quite messy - it contains punctiation, accented letters and numbers. For our analysis, we are only interested in our 27-character alphabet (i.e. 'a' through 'z' plus ' '). We are going to clean the data using the Julia function filter.

filter takes two arguments: a function and a collection. The function is applied to each element of the collection, and it returns either true or false. If the result is true, then that element ends up in the final collection.

Did you notice something cool? Functions are also just objects in Julia, and you can use them as arguments to other functions! (Fons thinks this is super cool.)

We have written a function isinalphabet, which takes a character, and returns a boolean:

👉 Use filter to extract a just the characters from our alphabet out of messy_sentence.

We are not interested in the case of letters ('A' vs 'a'), so we want to map these to lowercase before we apply our filter. If we don't, all uppercase letters get deleted.

👉 Use the function lowercase to convert messy_sentence_2 into a lowercase string, and then use filter to extract only the characters from our alphabet.

Finally, we need to deal with accents - simply deleting accented charactersfrom the source text might deform it too much. We can add accented letters to our alphabet, but a simpler solution is to replace accented letters with the unaccented base character. We have written a function unaccent that does just that.

👉 Let's put everything together. Write a function clean that takes a string, and returns a cleaned version, where:

• accented letters replaced by their base characters

• uppercase converted to lowercase

• filtered to only contain characters from alphabet

Exercise 1.2 - Letter frequencies

We are going to count the frequency of each letter in this sample, after applying your clean function. Can you guess which character is most frequent?

The result is a 27-element array, with values between 0.0 and 1.0. These values correspond to the frequency of each letter.

sample_freqs[i] == 0.0 means that the $i$th letter did not occur in your sample, and sample_freqs[i] == 0.1 means that 10% of the letters in the sample are the $i$th letter.

To make it easier to convert between a character from the alphabet and its index, we have the following function:

👉 Which letters from the alphabet did not occur in the sample?

Now that we know the frequencies of letters in English, we can generate random text that already looks closer to English!

Random letters from the alphabet:

hnocqu ssqlhydfxlhvootfbouhmqristwvgrrzaiohgxjknobxuzaswlrknyacxterh lrpghgxnwxjncinkx fkaocyy jjwyxcuxaxqvzwipxmfxbcsimqmancjniycrghenablofof slpguoixtgcytmxnmwrnrwuwllqhqgjxpbvpmdkvxfmly nik weveswhajluexyajwbkjvbfeah gdnhaksashoeniljmdiqrumipklwnwfm sywyrqqiakekddldqulfgrjoxedgairmb ktuqideqvchuzgcwpqzonhysbsdncyunktkraqseviylmyjqftncmkxjnveuhuvdopkyrnpqraqapqcdbtwugchetl gczhw f pmgn izqqrvxg

Random letters at the correct frequencies:

vi aoei tlgir ncvssea epet v ihlife s hii defawsrrra tieeoa ctlw dseeseyt retttsgth euet nao eotweevrl ufdtti r ef t p snmeihgvnn a i soagsnfdgxssloikfontlmwa sf golamfih lv ehr ndiacotn forneuicsdn h l eeihifhneishsllleucvw rr ro har edardoateoeddh e uexdre htgnhttslg fine ire grecb dcsa rw lg sgy t sphmsl wlnrlnealur epgttdskrs tsdiyrn nitgfaareaistsst oocilettls tsala ese daf bece sn

By considering the frequencies of letters in English, we see that our model is already a lot better!

Our next observation is that some letter combinations are more common than others. Our current model thinks that potato is just as 'English' as ooaptt. In the next section, we will quantify these transition frequencies, and use it to improve our model.

Exercise 1.3 - Transition frequencies

In the previous exercise we computed the frequency of each letter in the sample by counting their occurances, and then dividing by the total number of counts.

In this exercise, we are going to count letter transitions, such as aa, as, rt, yy. Two letters might both be common, like a and e, but their combination, ae, is uncommon in English.

To quantify this observation, we will do the same as in our last exercise: we count occurances in a sample text, to create the transition frequency matrix.

What we get is a 27 by 27 matrix. Each entry corresponds to a character pair. The column corresponds to the first character, the row is the second pair. Let's visualize this:

Answer the following questions with respect to the cleaned English sample text, which we called first_sample. Let's also give the transition matrix a name:

👉 What is the frequency of the combination "th"?

👉 What about "ht"?

👉 Which letters appeared double in our sample?

👉 Which letter is most likely to follow a W?

👉 Which letter is most likely to precede a W?

👉 What is the sum of each row? What is the sum of each column? How can we interpret these values?"

We can use the measured transition frequencies to generate text in a way that it has the same transition frequencies as our original sample. Our generated text is starting to look like real language!

Random letters from the alphabet:

lxzmih ikwnfkd tomsbgzncmvvybvnwutgyic xqskkfx zpayhwhccgxngelaxwxkqyxcpqdfvjxrgkhbbetgcafunstlmitqvlmssaohyom kliqsorpfwyxzwurwbptqzlf uyzrsmwomskeaeggpgyqltsjsadunzyrshbhfuxuqkqfvihgabg ndiwmssneynazodscobuxnhhcsgiaxsnkwxflpwbxavldrdysjvumuxowylhijkfgrowjbvvqvwcpvhediabuwmakjdqulbpvpsqpkom ewylvzvilmdqmdipgewojeucezwarioxtwlgmryrgpj gwcrmggajnxkosaygwfzbachagkxhgdwsxchrzkolnlq weioz rimubvzhdspp

Random letters at the correct frequencies:

ihsonga isagn m nrroslnetuaa rnme ciwchn fsg iosgtnda asnr oedleywah fmitpkc s h nselrn e esllli orhthgn rdti ac roeiilo eid csft d maelanwti f u twerdhi vi ro niotenolobitallae idisnanotn lelrianierersf nhaahateoaegey eannhttefm s nsnncnninoaylsln sihrmlo trhoecsroatrsb r ovceotdtft aaslthsvihc geto rsnfttiruhswsstc terto n eg nedo t frrsed odaheaa r tiiea eett uuynn oll luo hlfi

Random letters at the correct transition frequencies:

ivalylit ane orinleg oty n ive thayproma witire poth anotarefore t oyland te itisinckin fot t oprengingee cesprostho fls are t est sitisinivatrerdly orenagugiren min d fore wore re cialvesesiespr lis sexpog cas pr ofore glyarderreniore ind tinges ange t roreth ss orosionesefouly flva by uanored in teren m r ca f n wogils than ouesitorlisensthesthithe frevalve ofofilalin piorommalyan impespestinthol

Exercise 1.4 - Language detection

It looks like we have a decent language model, in the sense that it understands transition frequencies in the language. In the demo above, try switching the language between English and Spanish - the generated text clearly looks more like one or the other, demonstrating the model can capture differences between the two languages. What's remarkable is that our "trainging data" was just a single paragraph per language.

In this exercise, we will use our model to write a classifier: a program that automatically classifies a text as either English or Spanish.

This is not a difficult task - you can get dictionaries for both languages, and count matches - but we are doing something much more cool: we only use a single paragraph of each language, and we use a language model as classifier.

Let's compute the transition frequencies of our mystery sample! Type some text in the box below, and check whether the frequency matrix updates.

Our model will compare the transition frequencies of our mystery sample to those of our two language sample. The closest match will be our detected language.

The only question left is: How do we compare two matrices? When two matrices are almost equal, but not exactly, we want to quantify their distance.

👉 Write a function called matrix_distance which takes 2 matrices of the same size and finds the distance between them by:

1. Subtracting corresponding elements

2. Finding the absolute value of the difference

3. Summing the differences

We have written a cell that selects the language with the smallest distance to the mystery language. Make sure sure that matrix_distance is working correctly, and scroll up to the mystery text to see it in action!

Further reading

It turns out that the SVD of the transition matrix can mysteriously group the alphabet into vowels and consonants, without any extra information. See this paper if you want to try it yourself! We found that removing the space from alphabet (to match the paper) gave better results.

Exercise 2 - Language generation

Our model from Exercise 1 has the property that it can easily be 'reversed' to generate text. While this is useful to demonstrate its structure, the produced text is mostly meaningless: it fails to model words, let alone sentence structure.

To take our model one step further, we are going to generalize what we have done so far. Instead of looking at letter combinations, we will model word combinations. And instead of analyzing the frequencies of bigrams (combinations of two letters), we are going to analyze $n$-grams.

Dataset

This also means that we are going to need a larger dataset to train our model on: the number of english words (and their combinations) is much higher than the number of letters.

We will train our model on the novel Emma (1815), by Jane Austen. This work is in the public domain, which means that we can download the whole book as a text file from archive.org. We've done the process of downloading and cleaning already, and we have split the text into word and punctuation tokens.

Exercise 2.1 - bigrams revisited

The goal of the upcoming exercises is to generalize what we have done in Exercise 1. To keep things simple, we split up our problem into smaller problems. (The solution to any computational problem.)

First, here is a function that takes an array, and returns the array of all neighbour pairs from the original. For example,

bigrams([1, 2, 3, 42])

gives

[[1,2], [2,3], [3,42]]

👉 Next, it's your turn to write a more general function ngrams that takes an array and a number $n$, and returns all subsequences of length $n$. For example:

ngrams([1, 2, 3, 42], 3)

should give

[[1,2,3], [2,3,42]]

and

ngrams([1, 2, 3, 42], 2) == bigrams([1, 2, 3, 42])